// 欧拉筛求最小质因数
// 快速分解质因数
// 快速求所有因子
// https://soj.turingedu.cn/problem/50503/

bool visit[maxn];
int pri[maxn], psiz;  // 质数表
int pre[maxn];        // pre[i] 是 i 的最小质因数

void get_prime(int n) {  // 欧拉筛
    visit[0] = visit[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!visit[i]) pri[++psiz] = i, pre[i] = i;
        for (int j = 1; j <= psiz; ++j) {
            ll tmp = (ll)i * pri[j];
            if (tmp > n) break;
            visit[tmp] = 1, pre[tmp] = pri[j];
            if (i % pri[j] == 0) break;  // 在此跳过一部分
            // i * p[j2] = (k * p[j1]) * p[j2] = p[j1] * (k * p[j2])
            // 因为 p[j1] < p[j2]，所以等到 (k * p[j2]) 时再筛
        }
    }
}

vector<pair<ll, int>> d;            // 唯一分解， {p, c}
void get_prime_factor(ll remain) {  // 快速分解质因数，max_size > sqrt(n)
    d.clear();
    for (int i = 1; i <= psiz; ++i) {
        if (remain < max_size) break;  // 可以开始快速分解
        int p = pri[i], cnt = 0;
        while (remain % p == 0)
            ++cnt, remain /= p;
        if (cnt) d.push_back({p, cnt});
    }
    if (remain >= max_size) {  // 还剩一个大质数
        d.push_back({remain, 1});
    } else {  // 快速分解
        while (remain > 1) {
            int p = pre[remain], cnt = 0;
            while (remain % p == 0)
                ++cnt, remain /= p;
            d.push_back({p, cnt});
        }
    }
}

bool visit[maxn];     // 不是素数
int pri[maxn], psiz;  // 质数表
int pre[maxn];        // pre[i] 是 i 的最小质因数

vector<ll> ans;
void dfs(int dep, ll tmp) {  // 求质因数的自由组合
    if (dep >= d.size()) {
        ans.push_back(tmp);
        return;
    }
    ll p = d[dep].first;
    int c = d[dep].second;
    for (int j = 0; j <= c; ++j) {
        dfs(dep + 1, tmp);
        tmp *= p;
    }
}
